package com.techyuan.algorithm.utils;

import java.util.Random;

/**
 * Created by tianjuntao on 2016/11/30.
 */
public class SortUtils {
    public static void swap(int[] arr, int i, int j) {
        if (i == j)
            return;

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 对指定区域进行划分(随机主元)
     *
     * @param sortingArr 原数组
     * @param start      指定区域开始位置
     * @param end        指定区域结束为止
     * @return 返回指定区域end位置元素的位置
     */
    public static int randomizedPartition(int[] sortingArr, int start, int end) {
        int randomIndex = 1;
        swap(sortingArr, randomIndex, end);
        return partition(sortingArr, start, end);
    }

    public static int partition(int[] sortingArr, int start, int end, int pivotId) {
        swap(sortingArr, pivotId, end);
        return partition(sortingArr, start, end);
    }

    /**
     * 对指定区域进行划分（end位置数字作为主元）
     *
     * @param sortingArr 原数组
     * @param start      指定区域开始位置
     * @param end        指定区域结束为止
     * @return 返回指定区域end位置元素的位置
     */
    public static int partition(int[] sortingArr, int start, int end) {
        //选择末尾数字当做主元
        Integer x = sortingArr[end];
        int i = start - 1; //循环不变量的稳定值，代表左边划分区域的边界
        for (int j = start; j < end; j++) {
            if (sortingArr[j] <= x) {
                i = i + 1;
                swap(sortingArr, i, j);
            }
        }
        swap(sortingArr, i + 1, end);

        return i + 1;
    }

    public static int[] createRandomList(int count, int max) {
        int[] randomData = new int[count];
        Random random = new Random(System.currentTimeMillis());
        random.nextInt();
        for (int i = 0; i < count; i++) {
            randomData[i] = Math.abs(random.nextInt() % max);
        }

        return randomData;
    }
}
